# 归并排序
def merge_sort(num_list):
    length = len(num_list)
    print(num_list)
    # 递归终止退出条件
    if length <= 1:
        return num_list
    # 拆分
    mid = length // 2  # /2 普通除法，结果为浮点数 //2 整除
    # 对左侧的列表进行排序   1.递归中，左侧数据拆分完才执行下面的
    left_l = merge_sort(num_list[:mid])
    # 对右侧的列表进行排序  2.递归中，右侧数据拆分完才执行下面的
    right_l = merge_sort(num_list[mid:])
    print("left_l：{},right_l：{}".format(left_l, right_l))
    # 3.递归中，上面拆分完了才执行这下面的代码。最初都拆成了一个元素
    # merge 合并操作
    # 初始化两个指针p, q 初始位置为起始位置，初始化一个临时数组temp_list
    p, q, temp_list = 0, 0, list()
    # 计算当前被合并的列表的长度
    len_left, len_right = len(left_l), len(right_l)
    # 对左右两个数组进行排序，用临时数组存储  //p q指针的使用前提是left_l 和right_l是有序的
    while len_left > p and len_right > q:
        if left_l[p] <= right_l[q]:
            temp_list.append(left_l[p])
            p += 1
        else:
            temp_list.append(right_l[q])
            q += 1
    # 如果left 和 right_l 的长度不相等（ len_left > p and len_right > q才排序，q、p达到一方的长度后就停止了，会有一方长的没排），
    temp_list += left_l[p:]
    temp_list += right_l[q:]
    # 把长的部分直接追加到列表中

    return temp_list


if __name__ == '__main__':
    num_list = [6, 5, 3, 1, 8, 7, 2, 4]
    new_list = merge_sort(num_list)
    print('num_list:', new_list)

"""
执行过程：（控制台输出） 先拆分完最左边的->再排完最左边的->再拆分完最右边的->再排完最右边的->左右合并排完最后的
[6, 5, 3, 1, 8, 7, 2, 4]
[6, 5, 3, 1]
[6, 5]
[6]
[5]
left_l：[6],right_l：[5]
[3, 1]
[3]
[1]
left_l：[3],right_l：[1]
left_l：[5, 6],right_l：[1, 3]
[8, 7, 2, 4]
[8, 7]
[8]
[7]
left_l：[8],right_l：[7]
[2, 4]
[2]
[4]
left_l：[2],right_l：[4]
left_l：[7, 8],right_l：[2, 4]
left_l：[1, 3, 5, 6],right_l：[2, 4, 7, 8]
num_list: [1, 2, 3, 4, 5, 6, 7, 8]

执行步骤
第一步：拆分，除2除2不断的二分。分到不能分后开始排序。拆分过程如上。(所以递归层数为：log(底数2)（指数n）)
第二步：排序，设定两个指针，最初位置分别为两个已经排序（重点）序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
第四步：重复第三步直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾，完成一轮排序

时间复杂度
拆分的过程中不断二分，因此递归层数为：log(底数2)（指数n）
每层循环大约为：n次
时间复杂度为：O(nlogn)
"""
